Search Results

Documents authored by Rohwedder, Lars

Document
DOI: 10.4230/LIPIcs.STACS.2022.28
Cardinality Constrained Scheduling in Online Models

Authors: Leah Epstein, Alexandra Lassota, Asaf Levin, Marten Maack, and Lars Rohwedder

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Makespan minimization on parallel identical machines is a classical and intensively studied problem in scheduling, and a classic example for online algorithm analysis with Graham’s famous list scheduling algorithm dating back to the 1960s. In this problem, jobs arrive over a list and upon an arrival, the algorithm needs to assign the job to a machine. The goal is to minimize the makespan, that is, the maximum machine load. In this paper, we consider the variant with an additional cardinality constraint: The algorithm may assign at most k jobs to each machine where k is part of the input. While the offline (strongly NP-hard) variant of cardinality constrained scheduling is well understood and an EPTAS exists here, no non-trivial results are known for the online variant. We fill this gap by making a comprehensive study of various different online models. First, we show that there is a constant competitive algorithm for the problem and further, present a lower bound of 2 on the competitive ratio of any online algorithm. Motivated by the lower bound, we consider a semi-online variant where upon arrival of a job of size p, we are allowed to migrate jobs of total size at most a constant times p. This constant is called the migration factor of the algorithm. Algorithms with small migration factors are a common approach to bridge the performance of online algorithms and offline algorithms. One can obtain algorithms with a constant migration factor by rounding the size of each incoming job and then applying an ordinal algorithm to the resulting rounded instance. With this in mind, we also consider the framework of ordinal algorithms and characterize the competitive ratio that can be achieved using the aforementioned approaches. More specifically, we show that in both cases, one can get a competitive ratio that is strictly lower than 2, which is the bound from the standard online setting. On the other hand, we prove that no PTAS is possible.
Cite as

Leah Epstein, Alexandra Lassota, Asaf Levin, Marten Maack, and Lars Rohwedder. Cardinality Constrained Scheduling in Online Models. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{epstein_et_al:LIPIcs.STACS.2022.28,
  author =	{Epstein, Leah and Lassota, Alexandra and Levin, Asaf and Maack, Marten and Rohwedder, Lars},
  title =	{{Cardinality Constrained Scheduling in Online Models}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.28},
  URN =		{urn:nbn:de:0030-drops-158385},
  doi =		{10.4230/LIPIcs.STACS.2022.28},
  annote =	{Keywords: Cardinality Constrained Scheduling, Makespan Minimization, Online Algorithms, Lower Bounds, Pure Online, Migration, Ordinal Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.22
The Submodular Santa Claus Problem in the Restricted Assignment Case

Authors: Etienne Bamas, Paritosh Garg, and Lars Rohwedder

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned problem n unsplittable resources have to be assigned to m players, each with a monotone submodular utility function f_i. The goal is to maximize min_i f_i(S_i) where S₁,...,S_m is a partition of the resources. The result by Goemans et al. implies a polynomial time O(n^{1/2 +ε})-approximation algorithm. Since then progress on this problem was limited to the linear case, that is, all f_i are linear functions. In particular, a line of research has shown that there is a polynomial time constant approximation algorithm for linear valuation functions in the restricted assignment case. This is the special case where each player is given a set of desired resources Γ_i and the individual valuation functions are defined as f_i(S) = f(S ∩ Γ_i) for a global linear function f. This can also be interpreted as maximizing min_i f(S_i) with additional assignment restrictions, i.e., resources can only be assigned to certain players. In this paper we make comparable progress for the submodular variant: If f is a monotone submodular function, we can in polynomial time compute an O(log log(n))-approximate solution.
Cite as

Etienne Bamas, Paritosh Garg, and Lars Rohwedder. The Submodular Santa Claus Problem in the Restricted Assignment Case. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bamas_et_al:LIPIcs.ICALP.2021.22,
  author =	{Bamas, Etienne and Garg, Paritosh and Rohwedder, Lars},
  title =	{{The Submodular Santa Claus Problem in the Restricted Assignment Case}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.22},
  URN =		{urn:nbn:de:0030-drops-140912},
  doi =		{10.4230/LIPIcs.ICALP.2021.22},
  annote =	{Keywords: Scheduling, submodularity, approximation algorithm, hypergraph matching}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.42
Additive Approximation Schemes for Load Balancing Problems

Authors: Moritz Buchem, Lars Rohwedder, Tjark Vredeveld, and Andreas Wiese

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines. Additive approximation schemes compute a solution with an absolute error in the objective of at most ε h for some suitable parameter h and any given ε > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For these settings we present additive approximation schemes for h = p_{max}, the maximum processing time of the jobs. Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slot-MILP. While it has a linear number of integral variables, we identify structural properties of (near-)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a local-search algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most ε⋅ p_{max}.
Cite as

Moritz Buchem, Lars Rohwedder, Tjark Vredeveld, and Andreas Wiese. Additive Approximation Schemes for Load Balancing Problems. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{buchem_et_al:LIPIcs.ICALP.2021.42,
  author =	{Buchem, Moritz and Rohwedder, Lars and Vredeveld, Tjark and Wiese, Andreas},
  title =	{{Additive Approximation Schemes for Load Balancing Problems}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{42:1--42:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.42},
  URN =		{urn:nbn:de:0030-drops-141116},
  doi =		{10.4230/LIPIcs.ICALP.2021.42},
  annote =	{Keywords: Load balancing, Approximation schemes, Parallel machine scheduling}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.106
Knapsack and Subset Sum with Small Items

Authors: Adam Polak, Lars Rohwedder, and Karol Węgrzycki

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In this paper we focus on the maximum item size s and the maximum item value v. We give algorithms that run in time O(n + s³) and O(n + v³) for the Knapsack problem, and in time Õ(n + s^{5/3}) for the Subset Sum problem. Our algorithms work for the more general problem variants with multiplicities, where each input item comes with a (binary encoded) multiplicity, which succinctly describes how many times the item appears in the instance. In these variants n denotes the (possibly much smaller) number of distinct items. Our results follow from combining and optimizing several diverse lines of research, notably proximity arguments for integer programming due to Eisenbrand and Weismantel (TALG 2019), fast structured (min,+)-convolution by Kellerer and Pferschy (J. Comb. Optim. 2004), and additive combinatorics methods originating from Galil and Margalit (SICOMP 1991).
Cite as

Adam Polak, Lars Rohwedder, and Karol Węgrzycki. Knapsack and Subset Sum with Small Items. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 106:1-106:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{polak_et_al:LIPIcs.ICALP.2021.106,
  author =	{Polak, Adam and Rohwedder, Lars and W\k{e}grzycki, Karol},
  title =	{{Knapsack and Subset Sum with Small Items}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{106:1--106:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.106},
  URN =		{urn:nbn:de:0030-drops-141752},
  doi =		{10.4230/LIPIcs.ICALP.2021.106},
  annote =	{Keywords: Knapsack, Subset Sum, Proximity, Additive Combinatorics, Multiset}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.56
Robust Algorithms Under Adversarial Injections

Authors: Paritosh Garg, Sagar Kale, Lars Rohwedder, and Ola Svensson

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In this paper, we study streaming and online algorithms in the context of randomness in the input. For several problems, a random order of the input sequence - as opposed to the worst-case order - appears to be a necessary evil in order to prove satisfying guarantees. However, algorithmic techniques that work under this assumption tend to be vulnerable to even small changes in the distribution. For this reason, we propose a new adversarial injections model, in which the input is ordered randomly, but an adversary may inject misleading elements at arbitrary positions. We believe that studying algorithms under this much weaker assumption can lead to new insights and, in particular, more robust algorithms. We investigate two classical combinatorial-optimization problems in this model: Maximum matching and cardinality constrained monotone submodular function maximization. Our main technical contribution is a novel streaming algorithm for the latter that computes a 0.55-approximation. While the algorithm itself is clean and simple, an involved analysis shows that it emulates a subdivision of the input stream which can be used to greatly limit the power of the adversary.
Cite as

Paritosh Garg, Sagar Kale, Lars Rohwedder, and Ola Svensson. Robust Algorithms Under Adversarial Injections. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.ICALP.2020.56,
  author =	{Garg, Paritosh and Kale, Sagar and Rohwedder, Lars and Svensson, Ola},
  title =	{{Robust Algorithms Under Adversarial Injections}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{56:1--56:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.56},
  URN =		{urn:nbn:de:0030-drops-124632},
  doi =		{10.4230/LIPIcs.ICALP.2020.56},
  annote =	{Keywords: Streaming algorithm, adversary, submodular maximization, matching}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.18
Online Bin Covering with Limited Migration

Authors: Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, and Lars Rohwedder

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. This is motivated by the fact that the pure online model is often too restrictive to model real-world applications, where some changes might be allowed. A well-studied measure of the amount of decisions that can be revoked is the migration factor beta: When an object o of size s(o) arrives, the decisions for objects of total size at most beta * s(o) may be revoked. Usually beta should be a constant. This means that a small object only leads to small changes. This measure has been successfully investigated for different, classical problems such as bin packing or makespan minimization. The dual of makespan minimization - the Santa Claus or machine covering problem - has also been studied, whereas the dual of bin packing - the bin covering problem - has not been looked at from such a perspective. In this work, we extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case - where only insertions are allowed - and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worst-case migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio (up to an arbitrary small epsilon). We therefore resolve the competitiveness of the bin covering problem with migration.
Cite as

Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, and Lars Rohwedder. Online Bin Covering with Limited Migration. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{berndt_et_al:LIPIcs.ESA.2019.18,
  author =	{Berndt, Sebastian and Epstein, Leah and Jansen, Klaus and Levin, Asaf and Maack, Marten and Rohwedder, Lars},
  title =	{{Online Bin Covering with Limited Migration}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.18},
  URN =		{urn:nbn:de:0030-drops-111391},
  doi =		{10.4230/LIPIcs.ESA.2019.18},
  annote =	{Keywords: online algorithms, dynamic algorithms, competitive ratio, bin covering, migration factor}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.74
Local Search Breaks 1.75 for Graph Balancing

Authors: Klaus Jansen and Lars Rohwedder

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Graph Balancing is the problem of orienting the edges of a weighted multigraph so as to minimize the maximum weighted in-degree. Since the introduction of the problem the best algorithm known achieves an approximation ratio of 1.75 and it is based on rounding a linear program with this exact integrality gap. It is also known that there is no (1.5 - epsilon)-approximation algorithm, unless P=NP. Can we do better than 1.75? We prove that a different LP formulation, the configuration LP, has a strictly smaller integrality gap. Graph Balancing was the last one in a group of related problems from literature, for which it was open whether the configuration LP is stronger than previous, simple LP relaxations. We base our proof on a local search approach that has been applied successfully to the more general Restricted Assignment problem, which in turn is a prominent special case of makespan minimization on unrelated machines. With a number of technical novelties we are able to obtain a bound of 1.749 for the case of Graph Balancing. It is not clear whether the local search algorithm we present terminates in polynomial time, which means that the bound is non-constructive. However, it is a strong evidence that a better approximation algorithm is possible using the configuration LP and it allows the optimum to be estimated within a factor better than 1.75. A particularly interesting aspect of our techniques is the way we handle small edges in the local search. We manage to exploit the configuration constraints enforced on small edges in the LP. This may be of interest to other problems such as Restricted Assignment as well.
Cite as

Klaus Jansen and Lars Rohwedder. Local Search Breaks 1.75 for Graph Balancing. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ICALP.2019.74,
  author =	{Jansen, Klaus and Rohwedder, Lars},
  title =	{{Local Search Breaks 1.75 for Graph Balancing}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{74:1--74:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.74},
  URN =		{urn:nbn:de:0030-drops-106501},
  doi =		{10.4230/LIPIcs.ICALP.2019.74},
  annote =	{Keywords: graph, approximation algorithm, scheduling, integrality gap, local search}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.75
Near-Linear Time Algorithm for n-fold ILPs via Color Coding

Authors: Klaus Jansen, Alexandra Lassota, and Lars Rohwedder

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We study an important case of ILPs max {c^Tx | Ax = b, l <= x <= u, x in Z^{n t}} with n * t variables and lower and upper bounds l, u in Z^{nt}. In n-fold ILPs non-zero entries only appear in the first r rows of the matrix A and in small blocks of size s x t along the diagonal underneath. Despite this restriction many optimization problems can be expressed in this form. It is known that n-fold ILPs can be solved in FPT time regarding the parameters s, r, and Delta, where Delta is the greatest absolute value of an entry in A. The state-of-the-art technique is a local search algorithm that subsequently moves in an improving direction. Both, the number of iterations and the search for such an improving direction take time Omega(n), leading to a quadratic running time in n. We introduce a technique based on Color Coding, which allows us to compute these improving directions in logarithmic time after a single initialization step. This leads to the first algorithm for n-fold ILPs with a running time that is near-linear in the number nt of variables, namely (rs Delta)^{O(r^2s + s^2)} L^2 * nt log^{O(1)}(nt), where L is the encoding length of the largest integer in the input. In contrast to the algorithms in recent literature, we do not need to solve the LP relaxation in order to handle unbounded variables. Instead, we give a structural lemma to introduce appropriate bounds. If, on the other hand, we are given such an LP solution, the running time can be decreased by a factor of L.
Cite as

Klaus Jansen, Alexandra Lassota, and Lars Rohwedder. Near-Linear Time Algorithm for n-fold ILPs via Color Coding. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 75:1-75:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ICALP.2019.75,
  author =	{Jansen, Klaus and Lassota, Alexandra and Rohwedder, Lars},
  title =	{{Near-Linear Time Algorithm for n-fold ILPs via Color Coding}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{75:1--75:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.75},
  URN =		{urn:nbn:de:0030-drops-106518},
  doi =		{10.4230/LIPIcs.ICALP.2019.75},
  annote =	{Keywords: Near-Linear Time Algorithm, n-fold ILP, Color Coding}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.43
On Integer Programming and Convolution

Authors: Klaus Jansen and Lars Rohwedder

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
Integer programs with a constant number of constraints are solvable in pseudo-polynomial time. We give a new algorithm with a better pseudo-polynomial running time than previous results. Moreover, we establish a strong connection to the problem (min, +)-convolution. (min, +)-convolution has a trivial quadratic time algorithm and it has been conjectured that this cannot be improved significantly. We show that further improvements to our pseudo-polynomial algorithm for any fixed number of constraints are equivalent to improvements for (min, +)-convolution. This is a strong evidence that our algorithm's running time is the best possible. We also present a faster specialized algorithm for testing feasibility of an integer program with few constraints and for this we also give a tight lower bound, which is based on the SETH.
Cite as

Klaus Jansen and Lars Rohwedder. On Integer Programming and Convolution. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ITCS.2019.43,
  author =	{Jansen, Klaus and Rohwedder, Lars},
  title =	{{On Integer Programming and Convolution}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.43},
  URN =		{urn:nbn:de:0030-drops-101365},
  doi =		{10.4230/LIPIcs.ITCS.2019.43},
  annote =	{Keywords: Integer programming, convolution, dynamic programming, SETH}
}
Document
DOI: 10.4230/OASIcs.SOSA.2018.11
Compact LP Relaxations for Allocation Problems

Authors: Klaus Jansen and Lars Rohwedder

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)

Abstract
We consider the restricted versions of Scheduling on Unrelated Machines and the Santa Claus problem. In these problems we are given a set of jobs and a set of machines. Every job j has a size p_j and a set of allowed machines \Gamma(j), i.e., it can only be assigned to those machines. In the first problem, the objective is to minimize the maximum load among all machines; in the latter problem it is to maximize the minimum load. For these problems, the strongest LP relaxation known is the configuration LP. The configuration LP has an exponential number of variables and it cannot be solved exactly unless P = NP. Our main result is a new LP relaxation for these problems. This LP has only O(n^3) variables and constraints. It is a further relaxation of the configuration LP, but it obeys the best bounds known for its integrality gap (11/6 and 4). For the configuration LP these bounds were obtained using two local search algorithm. These algorithms, however, differ significantly in presentation. In this paper, we give a meta algorithm based on the local search ideas. With an instantiation for each objective function, we prove the bounds for the new compact LP relaxation (in particular, for the configuration LP). This way, we bring out many analogies between the two proofs, which were not apparent before.
Cite as

Klaus Jansen and Lars Rohwedder. Compact LP Relaxations for Allocation Problems. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:OASIcs.SOSA.2018.11,
  author =	{Jansen, Klaus and Rohwedder, Lars},
  title =	{{Compact LP Relaxations for Allocation Problems}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{11:1--11:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.11},
  URN =		{urn:nbn:de:0030-drops-83012},
  doi =		{10.4230/OASIcs.SOSA.2018.11},
  annote =	{Keywords: Linear programming, unrelated machines, makespan, max-min, restricted assignment, santa claus}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact